package 图论;

import java.lang.reflect.Array;
import java.util.*;

public class 并行课程3 {

    //拓扑排序   广度优先
    public int minimumTime(int n, int[][] relations, int[] time) {
        //统计一个节点的入度
        int[] inDegree = new int[n];
        List<Integer>[] graph =  new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] edge : relations) {
            int u = edge[0]-1;
            int v = edge[1]-1;
            //统计一个节点指向的节点
            graph[u].add(v);
            inDegree[v]++;
        }
        //统计每个节点完成时所需的时间
        int[] dist = new int[n];
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            //如果节点入度为0，则放入队列中
            if (inDegree[i]==0){
                queue.add(i);
                dist[i] = time[i];
            }
        }
        while (!queue.isEmpty()){
            Integer index = queue.poll();
            for (Integer next : graph[index]) {
                dist[next] = Math.max(dist[next],dist[index]+time[next]);
                //如果入度为0
                if (--inDegree[next] == 0)
                    queue.add(next);
            }
        }
        return Arrays.stream(dist).max().getAsInt();
    }
}
